#include<vector>
#include<iostream>

using namespace std;

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20,30};

    int bagweight = 4;

    // 创建dp数组 并 初始化
    vector<int> dp(bagweight + 1, 0);

    // 物品的遍历顺序是不影响的从前往后遍历，和从后往前遍历
    for(int i = 0; i < weight.size(); i++) {
    // for(int i = weight.size()-1; i >= 0; i--) {
        
        for(int j = bagweight; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j-weight[i]]+value[i]);
            cout<<"dp["<<j<<"] = "<<dp[j]<<" ";
        }
        cout<<endl;
    }

    cout<<"重量为："<<bagweight<<"的背包最多能装价值是:"<<dp[bagweight]<<endl;

    return;
}

int main() {
    test_1_wei_bag_problem();
}